Q1. Two-pointer 是什麼?

• 我個人認為雙指標 ( Two-pointer ) 比較像寫題目的技巧，一些演算法也會用到雙指標的概念，例如昨天介紹到的 Quick Sort，就有使用到雙指標的技巧
  • 雙指標主要可以分為兩種：

    • 快慢指標：兩個指標一起指向頭，或是一起指向尾，一個指標可能是按著順序走訪，一個是根據問題的需求來移動，讓指標會有快慢之分，他們都會一起向右移動，也稱為同向指標，類似 Quick Sort 的 Lomuto
      

    • 左右指標：兩個指標一個指向頭，一個指向尾，k 會向右移動，j 向左移動，兩個指標會逐漸靠近，也稱為反向指標，類似 Quick Sort 的 Hoare
      

Q2. 學會 Two-pointer 概念可以做什麼 ?

• 可以在以下情境考慮 Two pointer：
  • 題目禁止使用額外空間，原地交換值、比較
  • 題目給已經排序過的資料，然後對此資料進行一些操作，例如刪掉重複的元素等...
• 雙指標可以分為兩種：

  1. 快慢指標可以解決：

     • 將已經排序過的資料，把重複的元素刪掉

       

     • 判斷 linked list 是否有環，若是兩個指標相遇，代表有環

     

  2. 左右指標可以解決的題目類型：

     1. 反轉陣列，把 k 與 j 值交換

        

     2. 檢查 string 是否回文，檢查 k 位置的值 是否等於 j 位置的值

        

     3. 在已經排序過的資料中，題目會給一個 target ，找出資料中哪兩個數字相加為 target

        

     4. Quick Sort 的 Hoare 方法就是使用左右指標的概念將數字進行排序

        

Lab. 明天要解的題目：

• 明天要解的題目有兩題，分別是：
  • 26. Remove Duplicates from Sorted Array
  • 167. Two Sum II - Input array is sorted

26. Remove Duplicates from Sorted Array

• 題目連結：https://leetcode.com/problems/valid-parentheses/

• 題目敘述：

  • 題目會給你一個從小排序到大的資料，但是裡面有重複的元素，你需要把他刪掉
  • 有些語言是不能把資料裡的元素刪掉 ( array 長度不能被改變)，所以你需要把後面所有元素往前平移
  • 不過我們這邊使用的是 python，可以刪除任意位置的元素 ，所以只要遇到多餘的就刪掉即可，並且回傳刪完重複元素後的資料長度

  

• 測資的 Input/Output

  • 題目如果給你 [1,1,2] 那你要把多餘的元素刪掉，刪完重複元素後的資料長度

    

• 題目的條件

  • nums 裡的資料，會有 0~ 30000 個
  • 每一筆資料都會介於 -100~100
  • nums 裡的資料是經過排序的 (從小排到大)

  

167. Two Sum II - Input array is sorted

• 題目連結：https://leetcode.com/problems/valid-parentheses/

• 題目敘述：

  • 題目會給你一個從小排序到大的資料，跟希望找到的兩數相加的和 (target)

  • 你需要找出哪兩個位置的值，相加會等於 target

  • 哪兩個位置的值相加為 target，只會有一種答案

  • 同一個元素不能加兩次

    

• 測資的 Input/Output

  • 題目會給你一個遞增的數列，跟希望找到的目標總和 (target)

  • 回傳一個 list 結構的資料，裡面要包含相加會等於 target 的 index

    

• 題目的條件

  • 資料長度為 2~30000

  • 每一筆資料介於 -1000~1000

  • 資料由小排序到大

  • 相加的目標 (target) 介於 -1000~1000

  • 只會有唯一解